Nhà thám hiểm Tây Ban Nha Hernando de Soto đã viếng thăm khu vực của thành phố Tallahassee hiện nay trong mùa Đông 1539–1540 và tìm thấy một ngôi làng Apalachee. Sau gần 100 năm sau, những người thuộc Dòng Phanxicô đã thành lập 16 trụ sở hội truyền giáo ở khu vực, trong đó quan trọng nhất là San Luis de Talimali. Sau khi Hoa Kỳ chính thức giành được Florida từ Tây Ban Nha năm 1821, khu vực Tallahassee đã được chọn làm thủ phủ của lãnh thổ Florida do nó nằm trung độ của các trung tâm dân cư St. Augustine và Pensacola. Cơ quan lập pháp đã họp lần đầu ở Tallahassee năm 1824, và thành phố được thành lập năm 1825. Trong thời kỳ Nội chiến Hoa Kỳ (1861–1865), đây là thủ phủ Liên bang nằm ở phía Đông Sông Mississippi không bị quân Liên hiệp (Union) chiếm giữ. Tên gọi của cộng đồng được lấy từ ngôn ngữ Apalachee có nghĩa là "Phổ Cổ" hay "Cánh đồng bỏ hoang".